Three dimensional image computer graphics systems for rendering images are well known. A typical system (e.g. similar to the one represented in FIG. 4) projects and rasterizes polygons 401, and the resulting polygon fragments 402 are sorted in order to determine which are visible to the user and which are hidden. The sorting is typically carried out using a unit known as a depth buffer or z-buffer, 403. Depth or Z buffers are well known to those skilled in the art. Finally, the sorted fragments are written to a frame buffer 407, from where they may be displayed on a screen.
When a polygon is rendered to a frame buffer, the depth (or z-value) of each polygon fragment generated is compared against a current value in a depth buffer at the same location, and the fragment is only rendered, and the value in the depth buffer updated to the depth value of the fragment, if the fragment is found to be closer to the viewpoint than the current value in the depth buffer. As a result, when all polygon fragments have been considered, the depth buffer contains the depths and identities of the fragment closest to, and therefore visible to the viewer, for each pixel position in the frame buffer.
A conventional depth buffer requires a large memory, corresponding to the size of the frame buffer. This memory is typically so large that it must be stored in an external memory attached to the rendering device. A large number of polygon fragments are likely to be tested at each pixel position, leading to a very large number of memory accesses (reads and writes) to the depth buffer memory.
The memory bus connecting the external memory to the rendering device must have sufficient bandwidth to support the large number of accesses. The bus may also be shared with other parts of the system, such as the texturing unit, which will also generate large numbers of memory accesses. A large and fast memory subsystem is expensive, and so it is desirable to reduce the number of memory accesses wherever possible.
Three techniques can contribute towards reducing memory accesses and therefore implementing a depth buffer more efficiently in hardware: tiling, caching and compression.
The scope of this patent is depth buffer compression. In order to put this into context, depth buffer tiling and depth buffer caching, both well-known techniques, are also described. While it is envisaged that the depth buffer compression method would typically be used in conjunction with a cache, this is not a requirement.
In many systems, the frame buffer is subdivided into a plurality of rectangular areas or tiles. Fragments which are determined to be potentially visible in each tile are rendered to that tile. As fragments which do not cover a tile need to be rendered for that tile the number of depth buffer accesses is reduced as described below.
Depth Buffer Tiling
Depth buffers can be divided 401 into rectangular tiles by a tiling and rasterisation unit, for example 8 pixels by 8 pixels, the contents of each tile being stored contiguously in memory. If the closest and furthest depth values of previously rendered fragments for each tile are also stored, then for any new polygon, it is possible to check whether or not the points on the polygon overlapping the tile are hidden behind those already written to the tile in the depth buffer, and accordingly to choose not to render the polygon or to update the depth buffer and the stored closest and furthest depth values for the tile. When updating a depth buffer, testing for a hidden polygon can be performed efficiently because the polygon lies on a single plane, and only the corners of the tile (if they lie entirely within the polygon), the vertices of the polygon (if it lies entirely within the tile) or the points at which the polygon crosses the tile's edges need be checked to determine which is closest and which is furthest. If the points on the polygon overlapping the tile are all in front of what has already been written, closest and furthest depth values should both be updated. If some are in front, only the closest depth value is updated. If all are behind, the polygon is not written at all. Similar approaches are described in U.S. Pat. No. 6,037,946 (Takeda) and GB2378108 (Morphet).
Depth Buffer Caching
A depth buffer cache is shown in FIG. 4 at 404. A cache is an amount of storage space, small compared with main memory, but whose contents can be accessed much faster than they can from main memory. Its use reduces the frequency of main memory accesses when points close to each other in a buffer (here, the depth buffer) are accessed around the same time.
The cache is typically divided into lines, each of which is used to store the depth values of points close to each other. If tiling is used, each line might store all the values of a single tile or a single row or column of values of a tile. When a new tile whose contents are not currently in the cache are accessed, they are read into a cache line which is either unused, or more normally contains valid data which, if it has been modified, will first have to be evicted, i.e. written to Z buffer memory before the new tile is read from memory. The cache line selected might be one containing the least recently used data. The only other time the contents of a cache line are evicted is when the cache is flushed. This happens when the corresponding buffer is no longer being written to. Variations on the basic cache design are numerous and are well known.
If a tile's contents are stored in the cache, instead of reading them from memory or writing to them there, the cache line containing them is read or written instead. The underlying depth buffer in memory remains unaltered at this point, and is only accessed when a cache line is initialized or evicted.
One result of using a cache is that it decouples modification of pixel data from writing to memory, as writing to memory occurs during cache line evictions, which can occur as a result of a pixel read involving data absent from the cache triggering the eviction of the contents of another cache line whose data was least recently accessed. Similarly, reads from memory can occur as a result of modifying pixel data if the data is not currently present in the cache.